Computer systems required to display and edit documents typically require a software application to interpret the contents of a file on disk and format the file contents for display as a document. In most cases the contents of a document file on disk are encoded using a standardized encoding scheme. International text is commonly encoded using the Unicode standard published by Unicode Inc (The Unicode Standard, Addison-Wesley Developers Press, 2003. ISBN 0-321-18578-1). Document structure may also be encoded using a standardized encoding scheme such as XML published by the World-Wide-Web Consortium.
The Unicode standard provides means to encode international characters for many languages of the world with the intention of allowing display of files conforming to the Unicode standard. In general a Unicode file contains sequences of distinct characters whose value may be encoded using a single 32-bit word (UTF-32) or in a number of alternate encodings using a plurality of either 8-bit (UTF-8) or 16-bit (UTF-16) words. A single Unicode character may always be converted between any such encoding but alternate encodings always refer to a single Unicode character or code-point.
The display of Unicode on a computer display requires an application program to convert the Unicode characters into a form suitable for display. The display of internationalized text requires the mapping of Unicode characters into so-called ‘glyphs’ for output. Glyphs are outlines of written language that may be visually recognized by a reader of a given language. Mapping of Unicode characters to glyphs is not restricted to a 1:1 mapping, there being the common occurrence of multiple Unicode characters mapping to 1 glyph (m:1), a single Unicode character mapping to multiple glyphs (1:n) and multiple Unicode characters mapping to multiple glyphs (m:n).
A document display system capable of generating an image of a Unicode text document must first convert the characters into glyphs and then lay out the glyphs onto lines of text for display purposes. In different languages the written order of text may be visually different to the logical order. For example in Hebrew text the order of characters for written text is rightmost first and subsequent characters are written to the left of preceding characters, this is known as ‘right-to-left’ text. In English text the order of characters for written text is leftmost first and subsequent characters are written to right of preceding characters, this is known as ‘left-to-right’ text.
Mixing characters from different directionality such as a Hebrew quotation inside English text requires that the display program apply the Unicode Bidirectional Algorithm prior to display of glyphs (Davis, Mark. Unicode Technical Report #9: THE BIDIRECTIONAL ALGORITHM; http://www.unicode.org/reports/tr9/tr9-15.html). The Unicode Bidirectional algorithm as published teaches the steps required to correctly position output glyphs for an entire paragraph of character text. A paragraph is defined to be a contiguous group of characters containing no line or paragraph break character codes. Whilst the Bidirectional algorithm describes the processing required to lay out a paragraph of characters on an imaginary infinitely long line it omits description of how a mixture of bidirectional text may be broken into shorter lines of text. The Bidirectional algorithm further states that although the described processing steps are defined for application on entire paragraphs of text there is nothing preventing an implementation generating an equivalent result by the use of an incremental or piece-wise algorithm although no such incremental algorithms are presented.
Use of the Bidirectional algorithm requires classification of each Unicode character according to its bidirectional characteristics. In order to classify each character the Unicode Consortium provides a database of characteristics for each code point. As of Unicode Version 4.0 there are 96,382 defined code points. Each code point may be classified into one of 19 character types. The most common way to obtain the bidirectional character type for a Unicode character is to include a lookup table for each character. Given that most current computer systems operate on binary octets or 8-bit data, the size of such a table is large. For Unicode 4.0 it would consume 96,382 bytes at minimum. Alternate approaches to reducing the size of such a lookup table may include compression but the Unicode Specification does not disclose any applicable methods. Existing prior art methods that reduce the memory consumption for classification of a Unicode character include the binary tree approach whose classification requires storage of conditional range values and exhibits a lookup cost of log(N) comparisons resulting in a worst-case comparison depth of seventeen (17) comparison as well as the storage of comparison values at each node in the comparison tree, whilst the so-called perfect-hash approach stores a linear exception list which contains classification values for each exception character value whose classification is outside of the single largest classification set. A perfect-hash exception table for the bidirectional character properties in the Unicode character database encodes all the Unicode character values (for the exemplary version Unicode 4.0) whose classification is outside the dominant ‘left-to-right’ character type and consists of 5,124 entries, typically resulting in an encoded perfect-hash table of size 5,124 bytes, such a perfect hash exhibiting compact size but typically incurring a significant computational cost to compute the perfect-hash function as would be familiar to those skilled in the art of mathematical hash functions and computer science.
The Extensible Markup Language (XML) is a text based data serialization that facilitates structured storage of documents in a file on a computer system (Tim Bray et al. Extensible Markup Language (XML) 1.0 (Third Edition), W3C Recommendation 4 Feb. 2004; http://www.w3.org/TR/REC-xml/, Steven Pemberton et al. XHTML 1.0 The Extensible HyperText Markup Language. W3C Recommendation 26 Jan. 2000; http://www.w3.org/TR/2000/REC-xhtml1-20000126). XML builds on Unicode as the textual representation and adds structure to a document. Various XML vocabularies may be used to store any number of document types. For example World-Wide-Web pages may be codified in XHTML which is an XML compliant encoding of the so-called Hypertext Markup Language (HTML). XML may also be used as the file storage format for word processing documents as for example the WordML XML Schema produced by Microsoft Corporation for the encoding and storage of documents compatible with the Microsoft Word computer application program.
Interpretation of an XML vocabulary and display of an appropriate presentation to a user of a computer system requires decoding of the contents of an XML file and layout of such contents. The contents of an XML file may contain a mixture of Unicode text data as well as encoded images. Some XML file vocabularies may additionally reference external image data through a defined referencing mechanism for the vocabulary. The layout and display of such XML files is not described by the XML Recommendation however presentation guidelines may be published in other documents authored by various organizations.
The Cascading Style Sheets (CSS) Specification defines presentation characteristics for XML based documents (Bert Bos et al. Cascading Style Sheets, level 2 CSS Specification, W3C Recommendation 12-May-1998; http://www.w3.org/TR/REC-CSS2/). CSS supplies rules for matching an XML element name to the desired display characteristics for the element contents, such as font color, etc. CSS also provides mechanisms to specify the drawing order of objects inside an XML file.
Whilst the Unicode, XML, XHTML and CSS specifications define a model for display of document data through a series of rules and illustrations they do not provide algorithms for an application developer to utilize to achieve the desired output result image. Similarly many of the descriptions of display treat an XML document as a whole as no piece-wise modification of such a displayed document is described.
Layout and display of XML based documents such as XHTML in combination with CSS documents assume a tree-based data structure model which maps naturally onto a layered presentation model. These tree based models are ideal for batch layout of an entire document as layout constraints may be easily dealt with given an in-memory tree representation of a document. Computer display of a tree-based document model usually requires the application program to traverse the tree to build a so-called ‘flattened’ view of the tree as would be familiar to those skilled in the art of computer science. Such a flattened view translates the structured nodes in a tree into a linear presentation suitable for display purposes. The flattened view presents the user with logical linear flow such as, for example, lines of text structured firstly into paragraphs and then further into pages. Document editing and interaction at the computer display by a user usually requires interaction with the flattened view. Programmatically editing a tree-based document model usually requires modification of a sub-tree within the document and subsequent repeated layout of the entire document tree. CSS also supports the concept of Z-index which is a definition of the order in which sub-trees in the original document are painted with the result being a layered drawing representation under control of the document author. Editing such Z-indexed content can require redrawing the entire document tree after any modification. Handling partial updating of such a tree-based model for editing purposes is absent in all XHTML and CSS specifications as it is not considered as part of the design model for display of such documents.
The display of such documents usually consists of a mixture of Unicode text converted into glyphs and images interspersed according to some geometric rules. Such documents are not limited to XML based documents but are part of a broader category of document most commonly associated with so-called desktop publishing systems.
One characteristic of desktop publishing systems is the requirement that the document be modified interactively by a user of an application program on a computer system. When editing textual documents, it is common for the application program to display an indicator at the current insertion point in a document. This insertion point is known to those skilled in the art as a ‘caret’. The caret is commonly displayed to the user in some form that makes it visually distinguishable from the document itself. The caret may be displayed as a flashing or blinking object at a given insertion point.
The insertion point in a Unicode text document lies on the boundary of a Unicode character point. As a number of Unicode characters may generate (m:n) mappings, all Unicode characters are not necessarily textual delimiters for editing purposes. As user interaction with a document is performed on the displayed glyph presentation, selection of insertion point is done relative to glyph locations. A group of glyphs surrounded by text insertion locations suitable for caret placement are known as ‘grapheme clusters’. The caret is usually placed at the boundary of a grapheme cluster.
Most desktop publishing systems place a single caret at grapheme cluster boundaries. Should the boundary lie at the point of change of text display characteristics such as a change in font color, the insertion of text at the caret position usually follows a fixed rule as to which font characteristic is used to display the text insertion. For example, the font color of the text to the right of the caret may always be used to select the color for the inserted text. Should a continuous word contain mixed colors, a fixed rule is usually chosen to select the insertion text color as there is only one distinct caret position at each grapheme boundary.
When the caret lies at the boundary between text of different directionality it is common to choose the insertion direction corresponding to an application program setting that specifies the dominant text direction. For example if the caret were set to a point between a text display in Hebrew and a text display in English, the application could determine that Hebrew was the preferred text entry setting and insert characters into the Hebrew text complying with the needs of right-to-left text entry. Similarly, if the application setting was set to English dominant, then the text would be inserted adjacent to the English text in a left-to-right manner. Some systems also display a so-called ‘split’ caret with a partial caret displayed at both potential text insertion positions as an aid to the user of the application program. The user may then choose the dominant text direction manually to select the insertion position.
It is a deficiency in such document editing applications that the user must take additional steps to specify insertion font characteristics and/or text direction following the placement of the caret by use of a pointing device such as a mouse.